\documentclass[a4paper,11pt]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{subfigure}

\usepackage{listings}
\usepackage{float}
\usepackage{amsmath}

% Page de garde
\makeatletter
\def\maketitle{%
  \null
  \thispagestyle{empty}%
  \vfill
  \begin{center}\leavevmode
    \normalfont
    {\LARGE \@title\par}%
    \vskip 1cm
    {\Large \@author\par}%
    \vskip 1cm
    {\Large \@date\par}%
  \end{center}%
  \vfill
  \null
  \cleardoublepage
  }
\makeatother


\author{Guillaume Aouizerate, Dmitry Nesterenko et Jean-Bernard Jansen}
\date{}

\title{Ecriture d'un compilateur $\mu$java}

\begin{document}
\lstset{language=Pascal}
\maketitle

\section{Introduction}

Le but de ce projet est d’écrire un compilateur pour le langage $\mu$java, qui
est un sous-ensemble du langage java. Ce projet traite ainsi des 3 points
essentiels à la création d’un compilateur, qui sont le remplissage de la
table des symboles, le contrôle de type et la génération de code. Nous
utilisons pour traiter ces trois points une grammaire attribuée et le
langage Egg qui, avec son plugin Eclipse, nous permet de générer les
fichiers Java associés aux règles sémantiques des non-terminaux du
langage. Bien que notre compilateur ait été écrit de manière générique
pour convertir le code d’un programme $\mu$java vers n’importe quel langage
assembleur, c’est le langage TAM que nous avons choisi de développer dans
ce projet.

\section{Table des symboles}

Nous allons présenter dans cette section les grande lignes qui définissent notre gestion de la table des symboles.

\subsection{Structure générale choisie}

Tous les symboles utilisés et vérifiés sont véhiculés via deux attributs sémantiques hérités fondamentaux, à savoir \emph{tdc} et \emph{infoClasse}. Le premier contient toutes les classes qui ont été importées. Le second contient toutes les informations que nous connaissons déjà sur la classe en train d'être compilée. L'attribut \emph{infoClasse} contient la liste des attributs, des méthodes et des constructeurs. Les variables locales aux blocs sont stockées dans une table des variables qui est un attribut \emph{tdv} propre aux blocs. Nous avons largement usé de la généricité pour coder les classes Java nécessaires à l'utilisation de ces attributs. La classe de base s'appelle TDS et est étendue en TDV (table des variables), TDM (table des méthodes), TDA (table des attributs) et TDC (table des classes). Ces tables contiennent respectivement des éléments Info\_Variable, Info\_Methode, Info\_Attribut et Info\_Classe, toutes dérivées de la classe générique Info. Chacune de ces classes implémentent de nombreuses méthodes qui lui sont propre et que nous ne détaillerons pas. Le nom des méthodes est assez explicite pour celà. Le code est joint en annexe.explicite pour celà. Le code est joint en annexe.explicite pour celà. Le code est joint en annexe.explicite pour celà. Le code est assez explicite pour celà. Le code est joint en annexe.

\subsubsection{Structure de Info\_Variable}
% TODO guillaume
Info\_Variable contient un nom, un type, un déplacement et des getters sur ces paramètres. 

\subsubsection{Structure de TDM et Info\_Methode}

Celle-ci sont un peu particulières pour une raison très précise. La HashMap qui contient les méthodes n'est pas indexée par des objets \emph{String} mais par des objets \emph{CleMethode}, implémentés correctement pour pouvoir être utilisés comme des clés de HashMap. Pourquoi celà ? Parce qu'une méthode n'est en fait pas identifiée par son seul nom au sein de la classe, mais également par sa liste d'arguments, ou plus exactement, sa signature. L'objet \emph{CleMethode} permet donc de gérer une signature et de comparer diverses signatures. Celà simplifie grandement le procédé de recherche de symbole lors de l'utilisation de méthodes. TDM possède une autre grande particularité que nous développons dans la section \ref{gestion_ambiguites}.

\subsubsection{Structure de Info\_Attribut}
% TODO Guillaume
Info\_Attribut contient les informations décrivant un attribut : son type, son déplacement, son indice et sa visibilité. Il implante des getters pour ces paramètres.

\subsubsection{Structure de Info\_Classe}
% TODO Guillaume
Info\_Classe contient tous les constructeurs de la classe dans une TDM (Table Des Méthodes), ses méthodes dans une autre TDM, ses attributs dans une TDA (Table Des attributs) et ses classes internes dans une TDC (Table Des Classes). Une Info\_Classe peut aussi avoir une Info\_Classe parente, correspondant à l'utilisation du mot clé 'extends' dans la définition d'une classe.  
Info\_Classe est donc de loin la classe contenant le plus d'instructions puisqu'elle permet de manipuler toutes ces données. On peut ainsi rechercher des constructeurs, des méthodes ou des attributs localement (dans la classe elle-même), globalement en incluant la classe parente (si elle existe) à la recherche, ou uniquement dans la classe parente lors de l'utilisation de l'identifiant 'super'. Info\_Classe contient aussi des informations permettant la gestion des indices des attributs et des méthodes. Ces indices permettent de gérer les emplacements mémoires ainsi que les appels de méthode par liaison tardive. 
Additionnellement, cette classe contient une méthode lui permettant de s'enregistrer dans un fichier. Ce fichier sera alors réutilisé si la classe est importée dans une autre classe. On implémente donc aussi une méthode de chargement. 

\subsection{Gestion des \emph{imports}}

La table des symboles générée lors de la compilation de la classe est stockée dans un objet \emph{serializable} puis écrite dans un fichier qui porte le nom de la classe et porte l'extension \emph{.tds}. Celà rend les fichiers \emph{*.tds} compatible avec une seule et unique version du compilateur. Celà peut être gênant lors de l'utilisation de fichiers $\mu$java dont on ne connaît pas l'implémentation. Leur interface n'est pas normalisée comme elle l'est dans C avec les fichiers \emph{*.h}. C'est une fausse limitation car nous avons choisi cette solution pour gagner du temps. Parser un fichier d'interface ne représente qu'un travail supplémentaire lourd et sans intérêt dans notre cas. Notez que le fichier en question sert également pendant la seule compilation d'une seule classe. Ceci est expliqué dans la section \ref{section_double_passe}.

\subsection{Lien entre la TDS et la vérification des types}

Il se trouve qu'en $\mu$java, la gestion des type est très liée à la gestion de la table des symboles. On ne peut pas utiliser l'une sans l'autre, à partir du moment ou l'on considère qu'une classe représente un type. Bien que la vérification des symboles puisse être faite sans la vérification des types, les structures de données nécessaires à la vérification des types doivent être développées pour la gestion de la table des symboles. Ce travail a été effectué par deux personnes qui ont partagé table des symboles et vérification de type afin d'obtenir un maximum d'efficacité.

\subsection{Choix de la double passe}
\label{section_double_passe}

Au cours de nos réflexions sur la table des symboles, nous avons envisagé d'utiliser une table des futurs pour pouvoir gérer les attributs et méthodes déclarés plus bas dans le code source. Heureusement, avant d'avoir totalement implémenté celà, nous avons rencontré un obstacle : celà ne permet pas de connaître les types des symboles en question, ce qui signifie que nous aurions eu un problème pour la vérification des types. Nous avons donc fait le choix d'utiliser une compilation en deux passes. La première compilation n'affiche aucune erreur et récupère les méthodes et les attributs déclarés correctement. Pas les variables locales bien sûr, puisque celles-ci doivent être déclarées avant d'être utilisées. Nous disposons ensuite d'un attribut \emph{infoClasse2} qui contient la table de la classe complète si on est dans la deuxième passe, une table vide mais valide sinon. Nous pouvons aussi tester si nous nous trouvons dans la seconde ou première passe, mais nous ne le faisons pas systématiquement à cause des fourches dans le code que celà implique. Après mise en place de cette solution, elle s'est montrée tout à fait satisfaisante. Notez que nous avons intégré cette double passe dans le code java du compilateur, et qu'il n'est donc nullement nécessaire d'appeller la compilation deux fois.

\section{Vérification de type}

La vérification de type se fait à de nombreux niveaux. Basiquement, dans les expressions calculées, mais aussi dans les affectations, les retours de méthodes, etc.

\subsection{Deux familles de types}

Nous avons utilisé un objet \emph{Type} qui gère deux familles de types. La première est les types de base, à savoir int, bool et void. La raison de la présence de void est expliquée en \ref{le_type_void}.

\subsection{Void est un type}
\label{le_type_void}

Nous avons choisi d'intégrer void à la liste des types de base car celà nous simplifie la vérification de type. En effet, comme il n'existe pas dans la grammaire pour les variables, on ne crée pas de variables de type void, et l'utilisation de void dans une expression à calculer génère automatiquement une erreur.

\subsection{Casting automatique}

$\mu$java ne fournit pas dans sa grammaire le nécessaire pour effectuer des casting. Nous avons décidé de ne pas modifier la grammaire et de conserver cette limitation. Cependant, si aucune conversion de type n'est possible, on peut difficilement profiter de l'intérêt de la programmation objet. C'est pourquoi $\mu$java supporte la conversion automatique de type. 

\subsection{Gestion des ambiguités}
\label{gestion_ambiguites}

Nous avons implanté dans $\mu$java le support du casting automatique pour les appels de méthode. Le souci est que le casting automatique peut provoquer des ambiguités. En effet, si l'appel peut être casté à plusieurs méthodes existantes, $\mu$java ne saura pas laquelle choisir. Il générera donc une erreur en signalant précisément le type qu'il a trouvé pour l'appel et les choix entre lesquels il n'a pu décider. Cette détection n'est cependant pas aussi puissante que celle de Java, car Java calcule le nombre de conversion de types nécessaires aux appels et choisi la méthode qui permet le moins de conversion de types. Il ne génère une erreur que si plusieurs méthodes entrent alors en conflit. $\mu$java ne fait pas le calcul du nombre de conversions de types. Il génère une erreur dès que plusieurs méthodes peuvent être appellées via la conversion de type automatique.

\subsection{Gestion fine des returns}
% TODO par Guillaume
Une vérification poussée est effectuée sur les retours de fonctions. Tout d'abord, une erreur est levée lorsque l'on renvoie un type différent de celui qui est dans la signature de la méthode. On vérifie aussi que toutes les méthodes (pas les procédures) renvoient bien quelque chose. Une méthode est valide de ce point de vue si tous les traitements et contrôles de la méthode amènent nécessairement à une instruction return. On effectue donc des vérifications de retours dans toutes les boucles if/then/else.

~\\
\begin{table}[H]
\begin{tabular}{cc}
\begin{lstlisting}[title={~}]
public int methode(){
    if(true){
        return 0;
    }else{
        return 1;
    }
}
\end{lstlisting} &
\begin{lstlisting}[title={~}]
public int methode(){
    if(true){
        return 0;
    }else{
    }
}
\end{lstlisting}\\
\end{tabular}\\
\begin{center}
\title{Méthode correcte à gauche et incorrecte à droite}
\end{center}
\end{table}
~\\

\section{Génération de code}

\subsection{Organisation du code}
    A la génération du code on suppose que les classes à compiler sont correctes (c'est vérifié en partie par le typage) pour cette raison le code généré à la première passe ou à la compilation d'une classe incorrecte risque d'être incomplet et peut contenir la chaine de caractère "null".
    Le code est généré de façon à ce qu'on puisse obtenir un programme complet juste en concaténant les fichiers *.tam. Chaque partie du code (constructeur, fonction, …) est repéré par un label unique ce qui permet de garantir le bon fonctionnement du code indépendamment de la position des classes dans le fichier final.

\subsection{Représentation de la classe en mémoire}
    Lors de l'exécution une classe est représentée par une zone de mémoire dans le tas qui permet de stocker les attributs de la classe ainsi que la table des virtuels qui permet de réaliser la liaison tardive.
    La table des virtuels est une table active, elle est situé dans la partie code du programme et constituée d'instructions du type JUMP label\_methode. Elle est repérée dans le code par un label.
    L'ensemble des fonctions et de constructeurs est situé dans le code repéré par un ensemble de labels uniques.

\subsection{Constructeurs}
    Nous avons essayé de concevoir la structure des constructeurs de façon à ce qu'elle puisse s'adopter aux appels de super constructeurs (cette fonctionnalité n'est pas implémentée). En effet un constructeur a deux fonctionnalités l'allocation de mémoire et initialisation des données par le code spécifié dans le corps des constructeurs. Le problème qui se pose c'est que lors d'un appel de super(...) dans le constructeur d'une classe fille on ne doit pas allouer de mémoire. Pour cette raison nous avons séparé le code du constructeur en deux parties (allocation et initialisation). Nous allons voir le code généré pour l'exemple suivant :

\begin{lstlisting}[title={Une classe simple}]
class simple{
    int i1;
    int i2;

    public simple(){
        i1 = 1001;
        i2 = 1002;
    }

    public int i(){
        return i1;
    }
}

class sample extends simple{
    public int i;
    
    public sample(int e)
    {
        this.i = e;
    }
    
    public int inc(int a)
    {
        return a+1;
    }
    
    public void main()
    {
        sample s = new sample(5);
        int i = s.inc(1);
    }
}
\end{lstlisting}
Le code du constructeur qui est généré par notre compilateur est le suivant :

\begin{lstlisting}[title={Code TAM}]
sampledefault\_const ; constructeur par defaut
    LOADL 4
    SUBR MAlloc
    LOADA sample\_TDM
    LOAD (1) 3[LB]
    STOREI (1)
    RETURN (1) 0 

sample\_sample\_int\_1
    LOADL 4
    SUBR MAlloc
    LOADA sample\_TDM
    LOAD (1) 3[LB]
    STOREI (1)
    STORE (1) -1[LB]
    JUMP sample\_sample\_int\_2

sample\_sample\_int\_2
    LOAD (1) -1[LB]
    LOADL 3
    SUBR IAdd
    LOADA -2[LB]
    LOADI (1)
    LOAD (1) -2[ST]     ; on charge l'adresse en double
    STOREI (1)  ; affectation de donnees
    LOADI (1)   ; on recupere la valeur affectee
    POP (0) 1   ;on supprime le resultat calcule s'il n'est pas affecte
    POP (0) 0   ;suppressions des variables locales du bloc 
    LOAD (1) -1[LB]
    RETURN (1) 2
\end{lstlisting}

    On remarque qu'il y a le code supplémentaire généré, repéré par le label sampledefault\_const. Celui-ci est le code du constructeur par défaut. Pour l'instant ce constructeur n'est utilisé que pour le lancement de la fonction main.
    Le label sample\_sample\_int\_1 permet de repérer le code d'allocation de mémoire. Ce code alloue la mémoire pour stocker les attributs de la classe ainsi que le pointeur sur la table de virtuels. La réservation de la mémoire tient compte des attributs publics ou privés de la classe parente.
    Lors de l'exécution du constructeur l'adresse vers la zone mémoire (le "this") est gardée dans la case mémoire à l'adresse -1[LB]. Ca permet de faciliter la génération du code et ne pas différencier le cas de this dans une méthode ou du this dans un constructeur. L'espace mémoire pour la case mémoire -1[LB] est réservée juste avant l'appel au constructeur par la méthode appelante.



Fonctions
    Nous avons réalisé un compilateur qui tient compte de l'héritage et donc permet de gérer les appels liaisons tardives. En effet chaque instance d'une classe possède un pointeur vers la table des méthodes d'une classe (ce pointeur est situé dans la première case de la zone mémoire alloué pour un objet). Ainsi pour réaliser un appel de fonction sur une instance il suffit de :
~\\
\begin{itemize}
\item Charger l'adresse (@obj) à la quel est rangé cette instance.
\item Charger l'adresse @tm de la table des méthodes (elle se trouve à l'adresse @obj+0)
\item Calculer l'adresse correspondante à l'entrée de la fonction désirée (@tm + déplacement méthode)
\end{itemize}
~\\
    Dans la table les méthodes sont rangées dans un ordre précis. De façon à ce que la méthode m1 de la classe parente ait le même déplacement que la méthode m1 de la classe fille.
    Le passage des paramètres se fait par l'intermédiaire de la pile. En effet pour passer les paramètres à une fonction il suffit de les empiler juste avant de l'appel. Il est aussi important d'empiler l'adresse de l'instance d'objet sur la quelle on appel la fonction. On empile les paramètres dans l'ordre inverse (les derniers d'abord), l'adresse de l'objet est la dernière à être empilée (pour être sûr qu'elle est toujours à l'adresse –1[LB]).

Dans l'exemple précédent l'appel de méthode inc(1) se traduit par :

\begin{lstlisting}[title={Code TAM}]
; appel de la methode inc
    LOADL 1         ; chargement du litteral
    LOADL 0         ; lien statique (inutile ici)
    LOAD (1) -3[ST] ; on charge en haut de la pile l'adresse de l'objet sur 
                ; le quel on appel la methode
    POP (3) 1       ; supprimer le pointeur d'objet qui n'est plus util
    LOADL 2     ; deplacement dans la table des methodes
    SUBR IAdd       ; on calcule l'adresse 
    CALLI           ; appel de la methode

\end{lstlisting}

\subsection{Expressions}
Nous avons réalisé la génération de code de façon à ce que chaque expression laisse son résultat en haut de la pile. Ceci permet par exemple d'écrire le code comme par exemple :\\
~\\
\begin{center}
    a=(b=c)\\
\end{center}
~\\
Qui à a et b affecte le résultat de c.

\subsection{Expressions arithmétiques et logiques}

Chaque expression du type E1 @ E2 est transformé en un code assembleur qui permet de calculer le résultat de l'expression et de le mettre en haut de la pile. Et se traduit en TAM en

\begin{lstlisting}[title={Code TAM}]
;Code de E1
;Code de E2
SUBR NomSubroutine@
\end{lstlisting}

\subsection{Affectation}
    Une affectation a = b permet de calculer l'expression b et d'affecter le résultat à une attribut ou une variable décrite par l'expression a, elle renvoi aussi le résultat de b en haut de la pile de façon a ce que ce dernier puisse être réutilisé.



Dans l'exemple précédent l'affectation this.i = e; dans le constructeur de la classe sample se traduit par :

\begin{lstlisting}[title={Code TAM}]
    LOAD (1) -1[LB] ; this
    LOADL 3     ; indice de l'attribut i
    SUBR IAdd
    LOADA -2[LB]        ; parametre e
    LOADI (1)
    LOAD (1) -2[ST]     ; on charge l'adresse en double
    STOREI (1)      ; affectation de donnees
    LOADI (1)       ; on recupere la valeur affectee
    POP (0) 1       ; on supprime le resultat calcule s'il n'est pas affecte
\end{lstlisting}

\subsection{Gestion du main}
    Nous avons rajouté une fonctionnalité en plus qui permet de générer un bout de code qui lance la méthode main si elle existe dans une classe. Comme on n'a pas traité le cas des fonctions statique on a du créer une instance de la classe avant l'appel à la méthode. Ainsi en début du code de la classe sample on trouve :

\begin{lstlisting}[title={Code TAM}]
    CALL (LB) sampledefault\_const
    CALL (LB) sample\_main\_\_1
    HALT
\end{lstlisting}

Ce code appel le constructeur par défaut qui laisse en haut de la pile l'adresse du nouvel objet. Ensuit on appel la méthode main, qui pourra accéder à "this" et ainsi retrouver la table des virtuels.

\section{Aspects pratiques}

\subsection{Partage du travail}
Durant notre développement, Jean-Bernard et Guillaume ont travaillé simultanément sur la TDS et le contrôle de type, ces deux notions étant intimement liées. L'utilisation d'un svn, gérant très bien les conflits et fusions entre 2 versions d'un fichier, a permis ce travail simultané. Dimitri quant à lui a travaillé seul sur la génération de code. Jean-Bernard et Guillaume l'ont aidé pour les quelques problèmes liés à la TDS qui sont apparus. 
Les membres du groupe se sont réunis de nombreuses fois en TP et chez eux afin de traiter à plusieurs certains points compliqués ou pour se mettre au courant de l'avancement de leurs parties respectives ce qui a permis une évolution rapide du développement.

\subsection{Outils de développement}
Nous avons usé et abusé avec satisfaction de SVN et du plugin Eclipse pour EGG.

\subsection{Utilisation des \emph{ArrayList}}
Le nombre de traitements à effectuer lors de la création de la TDS et du contrôle de type est vite devenu si grand que la compilation prenait jusqu'à 10 secondes. Une amélioration a alors été apportée dans les classes utilisant la classe Vector de Java. Vector, issue d'une ancienne version de Java, permet l'ajout synchronisé de fichier, inutile ici, et lent par rapport à la classe ArrayList, qui date de Java 1.4. ArrayList implémente les mêmes méthodes mais est beaucoup plus rapide. Nous avons donc remplacé tous les Vector par des ArrayList et avons vu la vitesse de compilation multipliée par 5.

\subsection{Tests}

Nous avons écrit un fichier qui met en valeur les erreurs que notre compilateur détecte. Voici le code source de ce fichier :

\small
\lstset{title={Quelques erreurs parlantes},breaklines=true}
\lstinputlisting{../../examples/tests/erreurs.mj}
\normalsize

Et voici le résultat obtenu :   

\small
\lstset{title={Quelques erreurs parlantes},breaklines=true}
\begin{lstlisting}
version 0.0.1
Compiling ../examples/tests/erreurs
Premiere passe
Deuxieme passe
Premier
Deuxieme
../examples/tests/erreurs: 3: Semantic error: La classe Point a deja ete importee.
../examples/tests/erreurs: 51: Semantic error: La methode methodeSansRetour(bool,bool,bool) doit renvoyer un objet de type bool.
../examples/tests/erreurs: 56: Semantic error: La variable a existe deja dans la methode
../examples/tests/erreurs: 59: Semantic error: Identifiant private Point.y non visible depuis la classe PointCol
../examples/tests/erreurs: 62: Semantic error: Ne peut convertir bool en int (PointCol).
../examples/tests/erreurs: 63: Semantic error: La variable c existe deja dans la methode
../examples/tests/erreurs: 63: Semantic error: Ne peut convertir void en int (PointCol).
../examples/tests/erreurs: 64: Semantic error: L element a gauche d une affectation doit etre un attribut ou une variable.
../examples/tests/erreurs: 65: Semantic error: Les elements d'un calcul doivent etre des entiers.
../examples/tests/erreurs: 65: Semantic error: Ne peut convertir bool en int (PointCol).
../examples/tests/erreurs: 66: Semantic error: Les types des deux cotes de la comparaison doivent etre des entiers.
../examples/tests/erreurs: 66: Semantic error: Les elements d'un test doivent etre des booleens.  
../examples/tests/erreurs: 67: Semantic error: Seul un entier peut suivre un operateur unaire.
../examples/tests/erreurs: 68: Semantic error: L element a gauche d une affectation doit etre un attribut ou une variable.
../examples/tests/erreurs: 69: Semantic error: int est un type de base et n a ni attributs, ni methodes.
../examples/tests/erreurs: 77: Semantic error: La methode doit renvoyer un objet de type int.
../examples/tests/erreurs: 60: Semantic error: methodeAmbigue(PointCol,PointCol) : Appel de methode ambigu entre methodeAmbigue(PointCol,Point) et methodeAmbigue(Point,PointCol)  dans PointCol.
../examples/tests/erreurs: 61: Semantic error: La methode getIntMethode(int,int,int,int) de PointCol (PointCol) n'existe pas.
../examples/tests/erreurs: 70: Semantic error: La methode getxy() de Point (PointCol) n'existe pas.
../examples/tests/erreurs: 75: Semantic error: L identifiant f (PointCol) n'existe pas.
Ok.
\end{lstlisting}
\normalsize

\section{Conclusion}

Nous avons trouvé ce projet très satisfaisant car il a soulevé tous les
mystères que portait auparavant la compilation de programmes. Bien que
plus de temps eut été nécessaire pour résoudre les quelques bugs de notre
compilateur, et pour traiter la syntaxe complète de $\mu$java (utilisation du
static, utilisation complète du super, implantation d’un print ?), nous
sommes content de ce que nous avons réussi à mettre en place et de ce que nous avons appris.

\end{document}
